package net.tp.algo.sort;

import net.tp.struct.adt.SinglyNode;

import java.util.Comparator;

/**
 *
 * QuickSort for Singly Linked List.
 * <p>
 * For Singly Linked List, probably the best sorting is merge sort where it re-arrange the nodes (not elements) to make the elements in sorted order. This takes guaranteed $O(n \log n)$ time and it's a stable, in-place sort.
 * <p>
 * For QuickSort, the challenge of singly linked list is that we can only move forward. Also, we need to take care of cases where there can be multiple duplicate elements. Remember, a naive implementation may take quadratic time if there are many duplicate elements.
 * <p>
 * To tackle the multiple duplicate elements scenario, I maintain 3 regions divided by 2 pointers: {@code lt, gt}. Elements {@code [lo, lt)} are less than pivot element, elements {@code [lt, gt]} are equal to pivot element, elements {@code (gt, hi]} are greater than pivot element.
 * <p>
 * In a 3-way quicksort implementation, small values are pushed in the far left, large values in the far right and pivot values in the middle.
 *
 * <pre>{@literal
 *    lo   {e < pv}  lt  {e = pv}  i   {e ? pv}   gt  {e > pv}   hi
 * ---[--------------)-------------|--------------(--------------]---
 * }</pre>
 *
 * <p>
 * However, for singly linked list, I can only move forward, so I have to arrange the values as follow:
 *
 * <pre>{@literal
 *    lo   {e < pv}  lt  {e = pv}  gt  {e > pv}   i  {e ? pv}    hi
 * ---[--------------)-------------(--------------|--------------]---
 * }</pre>
 *
 * <p>
 * With this arrangement, if {@code i.element < pv}, I need to make two swap operations if the middle partition is not empty (i.e. {@code [lt, gt] != ⊘ or gt > lt}). To increase the chance that {@code gt = lt}, the pivot is pushed to the end so that it's encountered last.
 *
 * @author Trung Phan
 * @time $O(n \log n)$
 * @space $O(n)$
 *
 */
public class ListQuickSort {

    public static <E> void sort(SinglyNode<E> list, Comparator<? super E> comparator) {
        sort(list, tail(list), comparator);
    }

    private static <E> void sort(SinglyNode<E> lo, SinglyNode<E> hi, Comparator<? super E> comparator) {

        while (lo != hi) {

            SinglyNode<E> pivot = pivot(lo, hi, comparator);
            E pv = pivot.element;
            swap(pivot, hi); // push the pivot to the end so that we encounter it last.

            SinglyNode<E> lt = lo, lt_prev = null, gt = lo;
            int countLess = 0, countMore = 0;

            for (SinglyNode<E> i = lo; i != hi.next; i = i.next) {
                int c = comparator.compare(i.element, pv);
                if (c > 0) countMore++;
                else if (c == 0) {
                    swap(gt, i);
                    gt = gt.next;
                }
                else {
                    countLess++;
                    swap(lt, i);
                    if (lt != gt) swap(gt, i);
                    lt_prev = lt;
                    lt = lt.next;
                    gt = gt.next;
                }
            }

            // we need to sort 2 partitions: [lo - lt_prev] and [gt.next - hi]
            // select the smaller half to do the recursive.
            if (countLess <= countMore) {
                if (lt_prev != null) sort(lo, lt_prev, comparator);
                if (gt == hi) break;
                lo = gt.next;
            }
            else {
                if (gt != hi) sort(gt.next, hi, comparator);
                if (lt_prev == null) break;
                hi = lt_prev;
            }
        }
    }

    private static <E> void swap(SinglyNode<E> i, SinglyNode<E> j) {
        if (i != j) {
            E tmp = i.element;
            i.element = j.element;
            j.element = tmp;
        }
    }

    /**
     * Median of three strategy.
     * @param lo
     * @param hi
     * @param comparator
     * @param <E>
     * @return
     */
    private static <E> SinglyNode<E> pivot(SinglyNode<E> lo, SinglyNode<E> hi, Comparator<? super E> comparator) {

        SinglyNode<E> mid = mid(lo, hi);

        int c1 = comparator.compare(lo.element, mid.element);
        int c2 = comparator.compare(mid.element, hi.element);

        if (c1 <= 0) {
            if (c2 <= 0) return mid;
            else return comparator.compare(lo.element, hi.element) <= 0 ? hi : lo;
        }
        else {
            if (c2 > 0) return mid;
            else return comparator.compare(lo.element, hi.element) > 0 ? hi : lo;
        }
    }

    private static <E> SinglyNode<E> mid(SinglyNode<E> lo, SinglyNode<E> hi) {
        SinglyNode<E> mid = lo;
        for (SinglyNode<E> i = lo; i != null && i.next != null && i != hi && i.next != hi; i = i.next) {
            mid = mid.next;
        }
        return mid;
    }

    private static <E> SinglyNode<E> tail(SinglyNode<E> list) {
        if (list == null) return null;
        SinglyNode<E> tail = list;
        for (; tail.next != null; tail = tail.next);
        return tail;
    }

}
